//
// Created by ASUS on 2024/4/11/0011.
//

#include <bits/stdc++.h>
using namespace std;

int longestPalindromeSubseq(string s) {
	int n = s.length();
	vector<vector<int>> dp(n, vector<int>(n));
	for (int i = n - 1; i >= 0; i--) {
		dp[i][i] = 1;
		char c1 = s[i];
		for (int j = i + 1; j < n; j++) {
			char c2 = s[j];
			if (c1 == c2) {
				dp[i][j] = dp[i + 1][j - 1] + 2;
			} else {
				dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
			}
		}
	}
	return dp[0][n - 1];
}

int longestPalindromeSubseq1(string s) {
	int n=s.length();
	int dp[n][n];
	memset(dp,-1,sizeof(dp));
	function<int(int,int)> dfs=[&](int i,int j)->int{
		if(i>j) return 0;
		if(i==j){
			dp[i][j]=1;
			return 1;
		}
		if(dp[i][j]!=-1) return dp[i][j];
		if(s[i]==s[j]){
			dp[i][j]=dfs(i+1,j-1)+2;
			return dp[i][j];
		}else{
			dp[i][j]=max(dfs(i,j-1),dfs(i+1,j));
			return dp[i][j];
		}
	};
	return dfs(0,n-1);
}
